package _2022.hot100._301_删除无效的括号;

import java.util.ArrayList;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-05-26 16:47
 */
public class Solution {
    private List<String> res=new ArrayList<>();
    public List<String> removeInvalidParentheses(String s){
        int lremove=0;
        int rremove=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                lremove++;
            }else if(s.charAt(i)==')'){
                if(lremove==0){
                    rremove++;
                }else{
                    lremove--;
                }
            }
        }
        helper(s,0,lremove,rremove);
        return res;
    }

    private void helper(String str, int start, int lremove, int rremove) {
        if(lremove==0&&rremove==0){
            if(isVaild(str)){
                res.add(str);
            }
            return;
        }
        for(int i=start;i<str.length();i++){
            if(i!=start&&str.charAt(i)==str.charAt(i-1)){
                continue;
            }
            // 如果剩余的字符无法满足去掉的数量要求，直接返回
            if((lremove+rremove)>str.length()-i){
                return;
            }
            // 尝试去掉一个左括号
            if(lremove>0&&str.charAt(i)=='('){
                helper(str.substring(0,i)+str.substring(i+1),i,lremove-1,rremove);
            }
            // 尝试去掉一个左括号
            if(rremove>0&&str.charAt(i)==')'){
                helper(str.substring(0,i)+str.substring(i+1), i, lremove, rremove-1);

            }
        }
    }

    private boolean isVaild(String str) {
        int balance=0;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)=='('){
                balance++;
            }else{
                balance--;
            }
            if(balance<0){
                return false;
            }
        }
        return balance==0;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.removeInvalidParentheses("()())()"));
    }
}
